/*
EP3D is a real-time 3D planet engine , which in addition to providing 
substandard scene rendering and scene management, of course, it also 
provides some basic class libraries to build the entire virtual 
planet, or even the entire universe.

Copyright (C) 2010  Hongjiang Zhang	(zhjwyat@gmail.com)

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef EP3D_FREELIST_H
#define EP3D_FREELIST_H
#include "EP3DBase.h"
namespace EP3D
{
	#define FL_DEFAULT_RESERVE 20 

	enum {
		_ALIGN = 8
	};

	enum {
		_MAX_BYTES = 128
	};

	template <class T>
	class FreeList
	{
	private:
		union Obj {
			union Obj* FreeListLink;
			char Data[1];
		};

		struct Chunk {
			Chunk* Next;
			Obj* Objects;
		};

		Chunk*	m_pkStore;
		Chunk*	m_pkStoretail;
		Obj*	m_pkFreeList;
		uint	m_uiGrow;

		size_t RoundUp(size_t bytes) 
		{
			return (((bytes) + _ALIGN - 1) & ~(_ALIGN - 1)); 
		}

		void* Refill(size_t stSize)
		{
			char* pcBuffer = (char*)EP3DMalloc(m_uiGrow * stSize);
			Chunk* pkChunk = EP3DNew Chunk;
			pkChunk->Objects = (Obj*)pcBuffer;
			pkChunk->Next = NULL;
			if (NULL == m_pkStore) {
				m_pkStore = pkChunk;
			}
			else {
				m_pkStoretail->Next = pkChunk;
			}
			m_pkStoretail = pkChunk;

			Obj* pkResult;
			Obj* pkCur, * pkNext;
			int i;

			pkResult = (Obj*)pcBuffer;
			m_pkFreeList = pkNext = (Obj*)(pcBuffer + stSize);
			for (i = 1; ; i++) {
				pkCur = pkNext;
				pkNext = (Obj*)((char*)pkNext + stSize);
				if (m_uiGrow - 1 == i){
					pkCur->FreeListLink = NULL;
					break;
				}
				else {
					pkCur->FreeListLink = pkNext;
				}
			}

			return pkResult;
		}

	public:
		FreeList(uint uiGrow = FL_DEFAULT_RESERVE)
			:m_pkFreeList(NULL)
			,m_pkStore(NULL)
			,m_pkStoretail(NULL)
			,m_uiGrow(uiGrow)
		{
		}

		~FreeList()
		{
			Chunk* pkCur;
			Chunk* pkTemp;

			pkCur = m_pkStore;
			while (NULL != pkCur) {
				pkTemp = pkCur;
				pkCur = pkCur->Next;
				EP3DFree(pkTemp->Objects);
				EP3DDelete pkTemp;
			}
		}

		T* Allocate()
		{
			uint uiSize = sizeof(T);
			if (uiSize > (uint)_MAX_BYTES) {
				return EP3DNew T;
			}

			Obj* pkResult = m_pkFreeList;
			if (NULL == pkResult) {
				void* r = Refill(RoundUp(uiSize));
				return Construct(r);
			}

			m_pkFreeList = pkResult->FreeListLink;
			return Construct((void*)pkResult);
		}

		template<typename A1> 
		T* Allocate(A1 a1)
		{
			uint uiSize = sizeof(T);
			if (uiSize > (uint)_MAX_BYTES) {
				return EP3DNew T(a1);
			}

			Obj* pkResult = m_pkFreeList;
			if (NULL == pkResult) {
				void* r = Refill(RoundUp(uiSize));
				return Construct(r, a1);
			}

			m_pkFreeList = pkResult->FreeListLink;
			return Construct((void*)pkResult, a1);
		}

		template<typename A1, typename A2> 
		T* Allocate(A1 a1, A2 a2)
		{
			uint uiSize = sizeof(T);
			if (uiSize > (uint)_MAX_BYTES) {
				return EP3DNew T(a1, a2);
			}

			Obj* pkResult = m_pkFreeList;
			if (NULL == pkResult) {
				void* r = Refill(RoundUp(uiSize));
				return Construct(r, a1, a2);
			}

			m_pkFreeList = pkResult->FreeListLink;
			return Construct((void*)pkResult, a1, a2);
		}

		template<typename A1, typename A2, typename A3> 
		T* Allocate(A1 a1, A2 a2, A3 a3)
		{
			uint uiSize = sizeof(T);
			if (uiSize > (uint)_MAX_BYTES) {
				return EP3DNew T(a1, a2, a3);
			}

			Obj* pkResult = m_pkFreeList;
			if (NULL == pkResult) {
				void* r = Refill(RoundUp(uiSize));
				return Construct(r, a1, a2, a3);
			}

			m_pkFreeList = pkResult->FreeListLink;
			return Construct((void*)pkResult, a1, a2, a3);
		}

		template<typename A1, typename A2, typename A3, typename A4> 
		T* Allocate(A1 a1, A2 a2, A3 a3, A4 a4)
		{
			uint uiSize = sizeof(T);
			if (uiSize > (uint)_MAX_BYTES) {
				return EP3DNew T(a1, a2, a3, a4);
			}

			Obj* pkResult = m_pkFreeList;
			if (NULL == pkResult) {
				void* r = Refill(RoundUp(uiSize));
				return Construct(r, a1, a2, a3, a4);
			}

			m_pkFreeList = pkResult->FreeListLink;
			return Construct((void*)pkResult, a1, a2, a3, a4);
		}

		void Deallocate(T* pkObject)
		{
			if (NULL == pkObject) {
				return;
			}

			uint uiSize = sizeof(T);
			if (uiSize > (uint)_MAX_BYTES) {
				EP3DDelete pkObject;
			}

			Destroy(pkObject);

			Obj* pkTemp = (Obj*)pkObject;
			pkTemp->FreeListLink = m_pkFreeList;
			m_pkFreeList = pkTemp;
		}

		T* Construct(void* pMem)
		{
			return new(pMem) T;
		}

		template<typename A1>
		T* Construct(void* pMem, A1 a1)
		{
			return new(pMem) T(a1);
		}

		template<typename A1, typename A2>
		T* Construct(void* pMem, A1 a1, A2 a2)
		{
			return new(pMem) T(a1, a2);
		}

		template<typename A1, typename A2, typename A3>
		T* Construct(void* pMem, A1 a1, A2 a2, A3 a3)
		{
			return new(pMem) T(a1, a2, a3);
		}

		template<typename A1, typename A2, typename A3, typename A4>
		T* Construct(void* pMem, A1 a1, A2 a2, A3 a3, A4 a4)
		{
			return new(pMem) T(a1, a2, a3, a4);
		}

		void Destroy(T* pkObject)
		{
			pkObject->~T();
		}

	};
}

#endif